package huawei;

import java.util.LinkedList;
import java.util.Queue;

public class Test_0526 {

    public static void main(String[] args) {
        int[][] grid = {{1,0,0,0,0, 1,1,1},
                {1,0,0,0,0, 0,0,0},
                {0,1,0,0,1, 1,1,1},
                {1,1,0,0,0, 1,1,1}};
        System.out.println(findLargestOilField(grid));

    }

    private static int findLargestOilField(int[][] grid) {
        int rows = grid.length;
        int cols = grid[0].length;
        boolean[][] visited = new boolean[rows][cols];
        int maxArea = 0;
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                if (grid[i][j] == 1 && !visited[i][j]) {
                    int area = getArea(grid, visited, i, j);
                    maxArea = Math.max(maxArea, area);
                }
            }
        }
        return maxArea;
    }


    /**
     * 队列广度遍历法
     * 
     * @param grid
     * @param visited
     * @param i
     * @param j
     * @return 面积
     */
    private static int getArea(int[][] grid, boolean[][] visited, int i, int j) {
        Queue<int[]> queue = new LinkedList<>();
        queue.add(new int[]{i, j});
        visited[i][j] = true;
        // 上下左右四个方向搜索
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        int area = 0;
        while (!queue.isEmpty()) {
            int[] pos = queue.poll();
            area++;
            for (int[] dir : dirs) {
                int r = pos[0] + dir[0];
                int c = pos[1] + dir[1];
                // 移动后还在矩阵中
                if (r >= 0 && r < grid.length && c >= 0 && c < grid[0].length
                        // 之前没有搜索到且为 1 
                        && !visited[r][c] && grid[r][c] == 1) {
                    // 搜索到则加入队列中遍历时 area++
                    queue.add(new int[]{r, c});
                    // 标记为遍历过
                    visited[r][c] = true;
                }
            }
        }
        return area;
    }
}
